package com.wtgroup.demo.leetcode.q021_合并两个有序链表;

import com.wtgroup.demo.common.bean.LinkNode;
import com.wtgroup.demo.leetcode.org_bytedance.Q_合并两个有序链表;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/16 13:34
 */
public class Q021_Test {

    public static void main(String[] args) {
        // l1 = [1,2,4], l2 = [1,3,4]
        LinkNode[] inputs = {LinkNode.toListNode(1,2,4), LinkNode.toListNode(new int[]{1, 3, 4})};
        Solution_Iter exe = new Solution_Iter();
        LinkNode res = exe.mergeTwoLists(inputs[0], inputs[1]);
        LinkNode.print(res);
    }

    /**
     * [车撞]
     */
    private static class Solution_Iter {
        /**
         * 迭代
         * */
        public LinkNode mergeTwoLists(LinkNode l1, LinkNode l2) {
            // 套路: 为了返回用
            LinkNode dummyHead = new LinkNode();
            // 套路: 为了选取节点挂载用
            LinkNode tail = dummyHead;

            while (l1!=null && l2!=null) {
                if (l1.value > l2.value) {
                    tail.next = l2;
                    l2 = l2.next;
                } else {
                    tail.next = l1;
                    l1 = l1.next;
                }
                tail = tail.next;
                // tail.next = null; // 无需, 不会出现循环引用
            }

            // 剩余元素处理: 指针指下就可以了
            tail.next = l1 != null ? l1 : l2;

            return dummyHead.next;
        }
    }

    /**
     * 归并
     * [车撞]
     * @see Q_合并两个有序链表
     */
    private static class Solution_Merge {

        public LinkNode mergeTwoLists(LinkNode l1, LinkNode l2) {
            if (l1 == null || l2 == null) {
                return l1 == null ? l2 : l1;
            }

            LinkNode ans = null;
            if (l1.value <= l2.value) {
                ans = l1;
                l1 = l1.next;
            } else {
                ans = l2;
                l2 = l2.next;
            }
            ans.next = mergeTwoLists(l1, l2);

            return ans;
        }


    }

}
